#!/usr/bin/env python

def quick_sort(nums):
    def quick_sort_helper(nums, start, end):
        if start < end:
            pivot = partition(nums, start, end)
            quick_sort_helper(nums, start, pivot - 1)
            quick_sort_helper(nums, pivot + 1, end)
    
    quick_sort_helper(nums, 0, len(nums) - 1)

    return nums

def partition(nums, start, end):
    pivot = nums[start]

    left = start + 1
    right = end

    done = False
    while not done:
        while left <= right and nums[left] <= pivot:
            left += 1
        
        while right >= left and nums[right] >= pivot:
            right -= 1
        
        if right < left:
            done = True
        else:
            nums[left], nums[right] = nums[right], nums[left]
    
    nums[start], nums[right] = nums[right], nums[start]

    return right


if __name__ == "__main__":
    import random
    nums = [random.randint(0, 100) for _ in range(20)]
    print(nums)
    print(quick_sort(nums))